package org.correct.correcter;

import java.util.ArrayList;

public class BKTree {

	public BKNode tree;
	public String root = "a";
	public BKNode turn;
	public boolean hit = false;
	public BKTree()
	{
		tree =  new BKNode();
		tree.word = root;
		turn = tree;
	}
	/**
	 * 
	 * @param word
	 * @return
	 */
	public boolean Insert(String word,int population)
	{
		hit = false;
		turn = tree;
		
		if(Insert_word(word,population))
		{
			//System.out.println("insert"+word);
			return true;
		}
			
		else
			return false;
	}
	public boolean InsertHanyu(String word,String hanyu,int population)
	{
		hit = false;
		turn = tree;
		if(Insert_hanyu(word,hanyu,population))
		{
			return true;
		}
		else
			return false;
		
	}
	/**
	 * 
	 */
	public void ModifyPopulation(String word)
	{
		turn = tree;
		int distance = getDistance(turn.word,word);
		
		Modify_word(word,distance,turn);
	
	}
	public void ModifyPopulation(String word,String hanyu)
	{
		
		turn = tree;
		int distance = getDistance(turn.word,word);
		
		Modify_Hanyu(word,hanyu,distance,turn);
		
	}
	/**
	 * 
	 */
	public void Modify_word(String word,int distance,BKNode temp)
	{		
		
		//System.out.println(temp.word+"distance"+distance);
		if(getDistance(temp.word,word)==0)
		{
			temp.population++;
			return;
		}

		if(temp.sons.size() == 0)
			return;
		for(int i = 0; i < temp.sons.size(); i++)
		{			
		    if(temp.sons.get(i).distance == distance)
			{		
		    	Modify_word(word,distance,temp.sons.get(i));
				
			}
		    
		}
				
	}
	/**
	 * 
	 */
	public void Modify_Hanyu(String word,String hanyu,int distance,BKNode temp)
	{		
		
		//System.out.println(temp.word+"distance"+distance);
		if(getDistance(temp.word,word)==0)
		{
			for(int i = 0; i < temp.hanyu.size();i++)
			{
				if(temp.hanyu.get(i).equals(hanyu))
				{
					int newPopulation = Integer.parseInt(temp.hanyu.get(i)[1]);
					String [] newTemp = new String[2];
					newTemp[0] = temp.hanyu.get(i)[0];
					newTemp[1] = String.valueOf(newPopulation+1);
					temp.hanyu.set(i+1, newTemp);
					return;
				}
			}
		}
			
		if(temp.sons.size() == 0)
			return;
		for(int i = 0; i < temp.sons.size(); i++)
		{			
		    if(temp.sons.get(i).distance == distance)
			{		
		    	Modify_Hanyu(word,hanyu,distance,temp.sons.get(i));
				
			}
		    
		}
				
	}
	/**
	 * 
	 * @param word
	 * @return
	 */
	public boolean Insert_word(String word,int population)
	{
		String NodeString = turn.word;
		int distance = getDistance(word,NodeString);
		boolean contains = false;
		if(hit)
			return hit;
		if(distance == 0)
		{
			hit = true;
			return hit;
		}
		for(int i = 0; i < turn.sons.size(); i++)
		{			
		    if(turn.sons.get(i).distance == distance)
			{		
		    	contains = true;
				turn = turn.sons.get(i);
				Insert_word(word,population);
			}
		}
		if(!contains)
		{
			BKNode newNode = new BKNode();
			newNode.distance = distance;
			newNode.word = word;
			newNode.population = population;
			newNode.property = 0;
			turn.sons.add(newNode);
			//System.out.println(turn.sons.size());
			hit = true;		
			
		}
		return hit;
	}
	/**
	 * 
	 * @param word
	 * @param hanyu
	 * @return
	 */
	public boolean Insert_hanyu(String word,String hanyu,int population)
	{
		String NodeString = turn.word;
		int distance = getDistance(word,NodeString);
		boolean contains = false;
		if(hit)
			return hit;
		if(distance == 0)
		{
			hit = true;
			return hit;
		}
		for(int i = 0; i < turn.sons.size(); i++)
		{			
		    if(turn.sons.get(i).distance == distance)
			{		
		    	contains = true;
				turn = turn.sons.get(i);
				Insert_hanyu(word,hanyu,population);
			}
		}
		if(!contains)
		{
			BKNode newNode = new BKNode();
			newNode.distance = distance;
			newNode.word = word;
			String[] tempHanyu = new String[2];
			tempHanyu[0] = hanyu;
			tempHanyu[1] = String.valueOf(population);
			newNode.hanyu.add(tempHanyu);
			newNode.property = 1;
			turn.sons.add(newNode);
			//System.out.println(turn.sons.size());
			hit = true;		
			
		}
		return hit;
	}
	/**
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	
	public int getDistance(String s1, String s2)
	{
		char [] word1 = s1.toCharArray();
		char [] word2 = s2.toCharArray();
		int len1 = s1.length();
		int len2 = s2.length();
		int[][] distance = new int[len1+1][len2+1];
		for(int i = 0;i <= len1; i++)
		{
			distance[i][0] = i;
		}
		for(int i = 0; i <= len2; i++)
		{
			distance[0][i] = i;
		}
		for(int i = 1; i <= len1; i++)
			for(int j = 1; j <= len2; j++)
			{
				int samer = (word1[i-1]==word2[j-1]?0:1);
				int deleter = distance[i-1][j]+1;
				int inserter = distance[i][j-1]+1;
				int fix = distance[i-1][j-1]+samer;
				int temp = deleter;
				if(deleter > inserter)
					temp = inserter;
				if(fix < temp)
					temp = fix;
				distance[i][j] = temp;
					
			}
		return distance[len1][len2];
	}
	/**
	 * 
	 * @param word
	 * @return
	 */
	public ArrayList<String> Search(String word)
	{
		ArrayList<String> finalResult = new ArrayList<String>();
		ArrayList<BKNode> result = new ArrayList<BKNode>();
		turn = tree;
		int distance = getDistance(turn.word,word);
		int between = 0;
		while(result.size() == 0)
		{
			Search_word(word,distance,turn,between,result);
			turn = tree;
			between++;
			if(between > 5)
			{
				break;
			}
			//System.out.println("between=="+between);
		}
		

		for(int i = 0; i < result.size(); i++)
		{
			if(result.get(i).property == 1)
			{
				for(int j = 0; j < result.get(i).hanyu.size(); j++)
				{
					finalResult.add(result.get(i).hanyu.get(j)[0]);
					finalResult.add(result.get(i).hanyu.get(j)[1]);
					finalResult.add(String.valueOf(result.get(i).distance));
				}
			}
			else
			{
				finalResult.add(result.get(i).word);
				finalResult.add(String.valueOf(result.get(i).population));
				finalResult.add(String.valueOf(result.get(i).distance));
			}
		}
		return finalResult;
	}
	
	public ArrayList<String> Search(String word,String hanyu)
	{
		ArrayList<String> finalResult = new ArrayList<String>();
		ArrayList<BKNode> result = new ArrayList<BKNode>();
		//System.out.println("turn begin");
		turn = tree;
		int distance = getDistance(turn.word,word);
		//System.out.println("search begin");
		int between = 0;
		while(result.size() == 0)
		{
			Search_word(word,distance,turn,between,result);
			turn = tree;
			between++;
			if(between > 5)
			{
				break;
			}
			//System.out.println("between=="+between);
		}
		//System.out.println("search end");
		
		
		for(int i = 0; i < result.size(); i++)
		{
			for(int j = 0; j < result.get(i).hanyu.size(); j++)
			{
				finalResult.add(result.get(i).hanyu.get(j)[0]);
				finalResult.add(result.get(i).hanyu.get(j)[1]);
				finalResult.add(String.valueOf(result.get(i).distance));
			}
		}
		return finalResult;
	}
	public void Search_word(String word,int distance,BKNode temp,int between,ArrayList<BKNode> result)
	{		
		
		//System.out.println(temp.word+"distance"+distance);
		if(getDistance(temp.word,word)<=between)
			result.add(temp);

		if(temp.sons.size() == 0)
			return;
		for(int i = 0; i < temp.sons.size(); i++)
		{			
		    if((temp.sons.get(i).distance <= distance+between)||(temp.sons.get(i).distance >= distance-between))
			{		
		  		Search_word(word,distance,temp.sons.get(i),between,result);
				
			}
		    
		}
				
	}
}
